/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 言初
 * Date: 2023-11-15
 * Time: 21:40
 */

// 62. 不同路径

class Solution {
    public int uniquePaths(int m, int n) {
        // 动态规划
        //机器人只能向下移动和向右移动，所以说：
        //对于到达数组中任何一个位置的路径数==它左边格子的路径数+它上面格子的路径数
        //就对应于这个式子：dp[i][j]=dp[i][j-1]+dp[i-1][j]
        //也要注意这个数组的返回，在下标减一的时候要注意
        //因为这个机器人只能向下和向右,所以说对于我们新创建的dp数组来说，
        //这个数组的第一行和第一列可以先进行一下初始化的操作
        int[][] dp=new int[m][n];

        //先初始化 dp数组的第一行和第一列
        for(int i=0;i<m;i++){
            dp[i][0]=1;
        }
        for(int i=0;i<n;i++){
            dp[0][i]=1;
        }

        //开始转移填dp数组
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                dp[i][j]=dp[i][j-1]+dp[i-1][j];
            }
        }


        return dp[m-1][n-1];
    }
}
